package queue

import "errors"

var (
	ErrOutOfCapacity = errors.New("ekit: 超出最大容量限制")
	ErrEmptyQ        = errors.New("ekit: 队列为空")
)

// Comparator 用于比较两个对象的大小 x < y, 返回-1，x = y, 返回0，x > y, 返回1
type Comparator[T any] func(x, y T) int

// 用小顶堆实现的优先级队列，内部无锁，需要使用方加锁操作
type PriorityQueue[T any] struct {
	// 存放小顶堆的数组，数组下标为 0 的位置不存数据
	data     []T
	capacity int
	compare  Comparator[T]
}

func NewPriorityQueue[T any](capacity int, compare Comparator[T]) *PriorityQueue[T] {
	sliceCap := capacity + 1
	if capacity < 1 {
		capacity = 0
		sliceCap = 64
	}
	return &PriorityQueue[T]{
		capacity: capacity,
		data:     make([]T, 1, sliceCap),
		compare:  compare,
	}
}

func (q *PriorityQueue[T]) EnQueue(t T) error {
	if q.IsFull() {
		return ErrOutOfCapacity
	}
	// 把数据追加到堆尾，然后从堆尾元素开始，执行堆元素的上浮操作
	q.data = append(q.data, t)
	q.heapFloat(len(q.data) - 1)
	return nil
}
func (q *PriorityQueue[T]) DeQueue() (T, error) {
	if q.IsEmpty() {
		var t T
		return t, ErrEmptyQ
	}
	data := q.data[1]
	// 把堆尾元素的值赋值到堆顶元素，然后从堆顶元素开始执行堆的下沉操作
	q.data[1] = q.data[len(q.data)-1]
	q.data = q.data[:len(q.data)-1]
	q.heapSink(1, len(q.data))

	return data, nil
}
func (q *PriorityQueue[T]) heapFloat(i int) {
	// 任意位置的下标除以 2 都能得到父节点的下标
	child, parent := i, i/2
	for parent > 0 && q.compare(q.data[child], q.data[parent]) < 0 {
		q.data[child], q.data[parent] = q.data[parent], q.data[child]
		child = parent
		parent = child / 2
	}
}
func (q *PriorityQueue[T]) heapSink(i, n int) {
	// 任意位置的下标乘以 2 都能得到左子节点的下标
	var minIdx, left, right int
	for i < n {
		minIdx = i
		left = i * 2
		right = left + 1
		if left < n && q.compare(q.data[left], q.data[minIdx]) < 0 {
			minIdx = left
		}
		if right < n && q.compare(q.data[right], q.data[minIdx]) < 0 {
			minIdx = right
		}
		if minIdx == i {
			break
		}
		q.data[minIdx], q.data[i] = q.data[i], q.data[minIdx]
		i = minIdx
	}

}
func (q *PriorityQueue[T]) IsFull() bool {
	return q.capacity > 0 && len(q.data) == q.capacity+1
}
func (q *PriorityQueue[T]) IsEmpty() bool {
	return len(q.data) == 1
}
func (q *PriorityQueue[T]) Peek() (T, error) {
	if q.IsEmpty() {
		var t T
		return t, ErrEmptyQ
	}
	return q.data[1], nil
}
func (q *PriorityQueue[T]) Len() int {
	return len(q.data) - 1
}
